//
//  LCTwo.swift
//  LeetCode
//
//  Created by migu on 2021/7/13.
//  Copyright © 2021 LBB. All rights reserved.
//  给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
//  尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题

import Foundation
class LCTwo {
    func majorityElement(_ nums: [Int]) -> Int {
        
        //解法一：摩尔投票法
        var count:Int = 0
        var majoy:Int = nums[0]
        for i in 0..<nums.count {
            if count == 0 {
                count += 1
                majoy = nums[i]
            }
            if majoy != nums[i] {
                count -= 1
            }
            if majoy == nums[i] {
                count += 1
            }
        }
        return majoy
        
        //解法二：先排序，那么中间那个值，一定是大于 ⌊ n/2 ⌋ 的元素
        var nums:[Int] = nums
        for i in 0..<nums.count {
            for j in 0..<nums.count-1-i {
                let first:Int = nums[j]
                let second:Int = nums[j+1]
                let temp:Int = nums[j]
                if first > second {
                    nums[j] = nums[j+1]
                    nums[j+1] = temp
                }
//                if nums[j] > nums[j+1] {
//                    nums.swapAt(j, j+1)
//                }
            }
            
        }
        return nums[nums.count/2 + nums.count%2]
        
        
        var beforeConun:Int = 0
        var targerNum:Int = 0
        for i in 0..<nums.count {
            var numCount:Int = 0
            let temp:Int = nums[i]
            for j in 1..<nums.count {
                if temp == nums[j] {
                    numCount += 1
                }
            }
            if numCount > beforeConun {
                beforeConun = numCount
                targerNum = temp
            }
        }
        return targerNum
    }
}
